package com.notion.algorithms.datastructures;

public class UnionFind<T extends UnionFindable> {

	public void union(T component1, T component2){
		remarkLeaderVertexBasedOnSize(component1.getLeaderVertex(), component2.getLeaderVertex());
	}
	public UnionFindable find(T component){
		return component.getLeaderVertex();
	}
	/**
	 * Finds smaller of 2 leader trees and merges it in larger leader 
	 * @param leader1
	 * @param leader2
	 */
	private void remarkLeaderVertexBasedOnSize(UnionFindable leader1, UnionFindable leader2){
		if(leader1.getSubtreeSize()>=leader2.getSubtreeSize()){
			remarkLeaderVertex(leader1, leader2);
		}
		else{
			remarkLeaderVertex(leader2, leader1);
		}
	}
	/**
	 * Marks all vertices in child leader with leader vertex of parent leader
	 * @param parentLeader
	 * @param childLeader
	 */
	private void remarkLeaderVertex(UnionFindable parentLeader, UnionFindable childLeader){
		for(UnionFindable element:childLeader.getSubelements()){
			element.setLeaderVertex(parentLeader);
			parentLeader.getSubelements().add(element);
		}
	}
}
